Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Computing devices generally may perform mathematical operations such as addition, multiplication, and division. The manner in which mathematical operations are performed in hardware may affect the overall performance of the computing system.
Goldschmidt division is a technique for performing division in a computing device. Goldschmidt division is described, for example, in R. E. Goldschmidt, “Applications of Division by Convergence,” Master's thesis, M.I.T., 1964 and S. F. Oberman et al. “Division algorithms and implementations,” IEEE Trans. Computers, vol. 46, pp. 833-854, 1997, both of which are hereby incorporated by reference in their entirety for any purpose.
Goldschmidt division generally involves iteratively multiplying the numerator and denominator by a numerical factor. The numerical factor is selected or calculated to cause the denominator to converge towards unity. The product of the numerical factor and the numerator may then approximate the quotient.
For example, consider a division Q=N/D, where Q is the quotient, N is the numerator, and D is the denominator. To begin, both N and D are multiplied by an initial numerical factor F0. The numerical factor F0 may be selected from a stored table, and may be an approximate reciprocal of D to make the product F0D close to 1. Since F0 is selected from a finite number of choices stored in the table, the product F0D will have an error ε0=(1-D0). The approximated quotient following this initial multiplication may be represented as follows:
      Q    0    =                    N        ×                  F          0                            D        ×                  F          0                      =                  N        0                    1        -                  ɛ          0                    
At the i-th Goldschmidt iteration, the factor Fi and the quotient Qi may be computed as follows:
                    F        i            =                        (                      2            -                          D                              i                -                1                                              )                =                  1          +                      ɛ            0                          2                              i                -                1                                                          ;              Q      i        =                            N          i                          D          i                    =                                                  N                              i                -                1                                      ⁢                          F              i                                                          D                              i                -                1                                      ⁢                          F              i                                      =                                            N                              i                -                1                                      ⁡                          (                              1                +                                  ɛ                  0                                      2                                          i                      -                      1                                                                                  )                                            (                          1              -                              ɛ                0                                  2                  ⁢                  i                                                      )                              
The numerical factor Fi may be computed by taking a one's complement of Di-1, which may be convenient for machine applications. The one's complement generally refers to changing the value of each bit in a string of bits representing the value Di-1. The one's complement may be a relatively simple operation for processors, and accordingly it may compute numerical factors Fi in this manner.
As the iterations progress, Ni may converge toward Q with ever greater precision. Since the error of each iteration decreases by ε02i, the convergence order of Goldschmidt division is referred to as quadratic.
all arranged in accordance with at least some embodiments of the present disclosure.